245E - Mishap in Club - CodeForces Solution

/*
Problem URL:
https://codeforces.com/problemset/problem/993/A
*/
 
#include <bits/stdc++.h>
 
using namespace std;
 
void setIO(string s = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  if (s != "") {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
  }
}
 
// DEBUG INFO:
 
// helper for printing a pair
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
 
// helper for printing a container
template <typename T_container, typename T = typename enable_if<
                                    !is_same<T_container, string>::value,
                                    typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
  os << '{';
  string sep;
  for (const T &x : v)
    os << sep << x, sep = ", ";
  return os << '}';
}
 
// SHORTENED MACROS
#define ll long long
#define ull unsigned long long
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()
#define MOD 1000000007
#define x first
#define y second
 
// VERY USEFUL ORDERED CONTAINER TO USE INSTEAD OF STL
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(x)                                                         \
  tree<x, null_type, less<x>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset(x)                                                    \
  tree<x, null_type, less_equal<x>, rb_tree_tag, tree_order_statistics_node_update>
 
/*
 
Useful Links:
 
- the below link matches time complexity with input size
https://codeforces.com/blog/entry/21344
 
Problems to review for Silver:
https://codeforces.com/problemset?tags=combine-tags-by-or,binary%20search,data%20structures,two%20pointers,1700-2000

REALLY GOOD PROOFING WIKI:
http://zimmer.csufresno.edu/~larryc/proofs/proofs.html

CodeDrills Problem Recommender:
- https://recommender.codedrills.io/profile?handles=karthiksing05

Brainstorming:
 
Important Info:
- 

Thoughts:
- we can use an in set and an out set to keep track using the operations: if a
  given operation cannot be done, we can add a new person
 
- for a +, if we can't add somebody from the out set to the in set, we add a new
  person to the in set
- for a -, if we can't add somebody from the in set to the out set, we add a new
  person to the out set
  
- is a better solution the max number of signs that are the same at any
  given time LMAO that would be so funny: let's try that if this gets accepted

++-+-+++----+-++

In:


Out:
B
A
C
D

*/

string S;

int main(void) {
  
  setIO();
  
  cin >> S;
  
  int newGuy = 0;
  stack<int> inSet, outSet;
  
  for (auto ch : S) {
    
    if (ch == '+') {
      if (!(outSet.empty())) {
        inSet.push(outSet.top());
        outSet.pop();
      } else {
        inSet.push(newGuy);
        newGuy++;
      }
    } else {
      if (!(inSet.empty())) {
        outSet.push(inSet.top());
        inSet.pop();
      } else {
        outSet.push(newGuy);
        newGuy++;
      }
    }
  }
  
  cout << newGuy << "\n";
  return 0;
}